package dfs;

import java.util.Arrays;
import java.util.LinkedList;

public class 无重复字符串排列 {

    public String[] permutation(String s) {
        LinkedList<String> lists = new LinkedList<>();
        StringBuilder builder = new StringBuilder();
        boolean[] booleans = new boolean[s.length()];
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        dfs(lists,chars,builder,booleans);
        return lists.toArray(new String[lists.size()]);
    }

    private void dfs(LinkedList<String> list,char[] chars, StringBuilder builder,boolean[] booleans) {
        if (builder.length()==chars.length)
            list.add(builder.toString());
        for (int i = 0; i < chars.length; i++) {
            if (i>0 && chars[i]==chars[i-1] && !booleans[i-1])
                continue;
            if (!booleans[i]){
                booleans[i]=true;
                builder.append(chars[i]);
                dfs(list,chars,builder,booleans);
                builder.deleteCharAt(builder.length()-1);
                booleans[i]=false;
            }
        }
    }
}
